package sort; /**
 * description:
 * author:张腾
 * date:2021-03-26
 */

import java.util.Arrays;

/**
 * 归并排序  时间复杂度O(nlogn)
 * 缺点：以空间换时间
 */
public class Merge {
    //归并所需的辅助数组
    private static Comparable[] assist;

    public static void main(String[] args) {
        Integer[] a = new Integer[]{8,3,1,2,6,7};
        Merge.sort(a);
        System.out.println(Arrays.toString(a));
    }

    //比较v是否小于w ,true表示v<w
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w) < 0;
    }

    //数组元素i和j交换位置
    private static void exch(Comparable[] a,int i ,int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    //对数组a中的元素进行排序
    public static void sort(Comparable[] a){
        //初始化辅助数组
        assist = new Comparable[a.length];
        int lo = 0;
        int hi = a.length-1;
        sort(a,lo,hi);
    }

    //对数组a中从lo到hi的元素进行排序
    private static void sort(Comparable[] a,int lo ,int hi){
        if (hi<=lo) return;

        int mid = lo + (hi-lo)/2;   //5,9 mid=7
        //对每一组数据进行排序
        sort(a,lo,mid);
        sort(a,mid+1,hi);

        merge(a,lo,mid,hi);
    }

    //从lo到mid为一组，mid到hi为一组，对这两组数据进行合并
    //重点！！
    private static void merge(Comparable[] a,int lo ,int mid ,int hi){
        //定义三个指针
        int i = lo; //指向辅助数组
        int p1 = lo;
        int p2 = mid+1;

        //遍历，比较两个数组 ，排序并把结果放到辅助数组
        while(p1<=mid && p2<=hi){
            if (less(a[p1],a[p2])){
                assist[i++] = a[p1++];
            }else{
                assist[i++] = a[p2++];
            }
        }

        //其中一个数组还没有走到尾，则遍历赋值
        while (p1 <= mid){
            assist[i++] = a[p1++];
        }
        while (p2 <= hi){
            assist[i++] = a[p2++];
        }

        //将辅助数组拷贝回原数组
        for (int index=lo;index<=hi;index++){
            a[index] = assist[index];
        }
    }
}
